#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix,int target)
    {
        if(matrix.empty() || matrix[0].empty()) return false;

        int rows = matrix.size();
        int cols = matrix[0].size();

        int row = 0,col = cols-1;

        while(row<rows && col >= 0)
        {
            if(matrix[row][col] == target)
            {
                return true;
            }
            else if(matrix[col][row] > target)
            {
                col--;
            }
            else
            {
                row++;
            }
        }
        return false;
    }

};
int main()
{
    vector<vector<int>>matrix = 
    {
    {1, 4, 7, 11, 15},
    {2, 5, 8, 12, 19},
    {3, 6, 9, 16, 22},
    {10, 13, 14, 17, 24},
    {18, 21, 23, 26, 30}
    };
    int target = 5;
    Solution sol;
    bool result = sol.searchMatrix(matrix,target);
    cout<<result<<endl;
    return 0;
}